package com.alg;

import java.util.*;

/**
 * @author: sun.hongliang
 * @create: 2020/01/02 14:42
 */
public class ziji {
    private List<List<Integer>> res;

    private void find(int[] nums, int begin, Stack<Integer> stack) {
        res.add(new ArrayList<>(stack));
        for (int i = begin; i < nums.length; i++) {
            stack.push(nums[i]);
            find(nums, i + 1, stack);
            stack.pop();
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        int len = nums.length;
        res = new ArrayList<>();
        if (len == 0) {
            return res;
        }
        find(nums, 0, new Stack<>());
        return res;
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums == null || nums.length == 0) return Collections.emptyList();
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int[] vis = new int[nums.length];
        backTrace(nums, res, 0, new Stack<>(), vis);
        return res;
    }

    public void backTrace(int[] nums, List<List<Integer>> res, int start, Stack<Integer> stack, int[] vis) {
        res.add(new ArrayList<>(stack));
        for (int i = start; i < nums.length; i++) {
            if (i != 0 && nums[i] == nums[i - 1] && vis[i - 1] == 0) continue;
            stack.push(nums[i]);
            vis[i] = 1;
            backTrace(nums, res, i + 1, stack, vis);
            stack.pop();
            vis[i] = 0;
        }
    }

    public static void main(String[] args) {
        ziji solution = new ziji();
        int[] nums = {1, 2, 2};
        List<List<Integer>> subsets = solution.subsets(nums);
        subsets.forEach(System.out::println);
    }
}
